Search results for "finite [mass]"

Classical automata on promise problems

2015

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Secon…

Minimal forbidden factors of circular words

2017

Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactorial) sets of minimal forbidden factors. There exist algorithms for computing the minimal forbidden factors of a word, as well as of a regular factorial language. Conversely, Crochemore et al. [IPL, 1998] gave an algorithm that, given the trie recognizing a finite antifactorial language $M$, computes a DFA recognizing the language whose set of minimal forbidden factors is $M$. In the same paper, they showed that the obtained DFA is minimal if the input trie recognizes the minimal forbidden factors of a single word.…

Exact affine counter automata

2017

We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…

Groups with few $p'$-character degrees

2019

Abstract We prove a variation of Thompson's Theorem. Namely, if the first column of the character table of a finite group G contains only two distinct values not divisible by a given prime number p > 3 , then O p p ′ p p ′ ( G ) = 1 . This is done by using the classification of finite simple groups.

Conjugacy classes, characters and products of elements

2019

Recently, Baumslag and Wiegold proved that a finite group $G$ is nilpotent if and only if $o(xy)=o(x)o(y)$ for every $x,y\in G$ of coprime order. Motivated by this result, we study the groups with the property that $(xy)^G=x^Gy^G$ and those with the property that $\chi(xy)=\chi(x)\chi(y)$ for every complex irreducible character $\chi$ of $G$ and every nontrivial $x, y \in G$ of pairwise coprime order. We also consider several ways of weakening the hypothesis on $x$ and $y$. While the result of Baumslag and Wiegold is completely elementary, some of our arguments here depend on (parts of) the classification of finite simple groups.

Repetition times for Gibbsian sources

1999

In this paper we consider the class of stochastic stationary sources induced by one-dimensional Gibbs states, with Holder continuous potentials. We show that the time elapsed before the source repeats its first n symbols, when suitably renormalized, converges in law either to a log-normal distribution or to a finite mixture of exponential random variables. In the first case we also prove a large deviation result.

Linear Response Theory with finite-range interactions

2021

International audience; This review focuses on the calculation of infinite nuclear matter response functions using phenomenological finite-range interactions, equipped or not with tensor terms. These include Gogny and Nakada families, which are commonly used in the literature. Because of the finite-range, the main technical difficulty stems from the exchange terms of the particle–hole interaction. We first present results based on the so-called Landau and Landau-like approximations of the particle–hole interaction. Then, we review two methods which in principle provide numerically exact response functions. The first one is based on a multipolar expansion of both the particle–hole interactio…

Quantum inductive inference by finite automata

2008

AbstractFreivalds and Smith [R. Freivalds, C.H. Smith Memory limited inductive inference machines, Springer Lecture Notes in Computer Science 621 (1992) 19–29] proved that probabilistic limited memory inductive inference machines can learn with probability 1 certain classes of total recursive functions, which cannot be learned by deterministic limited memory inductive inference machines. We introduce quantum limited memory inductive inference machines as quantum finite automata acting as inductive inference machines. These machines, we show, can learn classes of total recursive functions not learnable by any deterministic, nor even by probabilistic, limited memory inductive inference machin…

Complexity of probabilistic versus deterministic automata

2005

Finite Alphabet Control of Logistic Networks with Discrete Uncertainty

2014

We consider logistic networks in which the control and disturbance inputs take values in finite sets. We derive a necessary and sufficient condition for the existence of robustly control invariant (hyperbox) sets. We show that a stronger version of this condition is sufficient to guarantee robust global attractivity, and we construct a counterexample demonstrating that it is not necessary. Being constructive, our proofs of sufficiency allow us to extract the corresponding robust control laws and to establish the invariance of certain sets. Finally, we highlight parallels between our results and existing results in the literature, and we conclude our study with two simple illustrative exampl…